package com.zklh.leetcode.top100;

import java.util.*;

/**
 * 分割回文串
 *
 * @version 1.0
 * @Author tongnan
 * @Date 2023/11/1
 */
public class Solution131 {
    private List<List<String>> allPartition;
    private int[][] f;

    public List<List<String>> partition(String s) {
        allPartition = new ArrayList<>();
        Deque<String> trace = new LinkedList<>();
        f = new int[s.length()][s.length()];
        for (int[] ints : f) {
            Arrays.fill(ints, 0);
        }
        dfs(trace, s, 0);
        return allPartition;
    }

    public void dfs(Deque<String> trace, String s, int start) {
        if (start >= s.length()) {
            allPartition.add(new ArrayList<>(trace));
            return;
        }
        int current = start;
        while (current < s.length()) {
            if (isPalindrome(s, start, current)) {
                trace.addLast(s.substring(start, current+1));
                dfs(trace, s, current+1);
                trace.removeLast();
            }
            current++;
        }
    }

    private boolean isPalindrome(String s, int start, int end) {
        if(f[start][end] == 1) {
            return true;
        }
        if (start >= end) {
            return true;
        }

        f[start][end] = s.charAt(start) == s.charAt(end) && isPalindrome(s, start+1, end -1) ? 1 : -1;
        return f[start][end] == 1;
    }

    public static void main(String[] args) {
        Solution131 solution131 = new Solution131();
        System.out.println(solution131.partition("abbab"));
    }
}